package com.leaf.spring.y201906.day25.arithmetic.hash;

import java.util.SortedMap;
import java.util.TreeMap;

import com.leaf.spring.y201906.day25.arithmetic.ServerIps;

/**
 * 一致性哈希算法
 * 
 * @Title:
 * @Description:
 * @Author: leaf
 * @Since:2019年6月26日
 * @Version:1.1.0
 */
public class ConsistentHashArith {

	// 虚拟节点、一致性hash环
	private static SortedMap<Integer, String> virtualNodes = new TreeMap<>();
	// 虚拟节点数
	private static final int VIRTUAL_NODES = 160;

	static {
		// 对每个真实节点添加虚拟节点，虚拟节点会根据哈希算法进行散列
		ServerIps.LIST.forEach(ip -> {
			for (int i = 0; i < VIRTUAL_NODES; i++) {
				int hash = getHash(ip + "VN" + i);
				virtualNodes.put(hash, ip);
			}
		});
	}

	public String getServer(String client) {

		int clientHash = getHash(client);

		// 得到大于该hash值的Map
		SortedMap<Integer, String> clientTailMap = virtualNodes.tailMap(clientHash);

		// 大于该值的第一个元素的位置
		Integer firstKey = clientTailMap.firstKey();

		// 如果不存在该hash值的元素，则返回根节点
		if (firstKey == null) {
			firstKey = virtualNodes.firstKey();
		}

		// 返回对应的虚拟节点名称
		return virtualNodes.get(firstKey);
	}

	/**
	 * 使用FNV1hash算法
	 * 
	 * @param key
	 * @return
	 * @Description:
	 */
	public static int getHash(String key) {

		final int p = 16777619;
		int hash = (int) 2166136261L;

		for (int i = 0; i < key.length(); i++)
			hash = (hash ^ key.charAt(i)) * p;
		hash += hash << 13;
		hash ^= hash >> 7;
		hash += hash << 3;
		hash ^= hash >> 17;
		hash += hash << 5;

		// 如果算出来的值为负数，则取绝对值
		if (hash < 0) {
			hash = Math.abs(hash);
		}

		return hash;
	}

	public static void main(String[] args) {

		for (int i = 0; i < 10; i++) {
			System.out.println(new ConsistentHashArith().getServer("client" + i));
		}

	}

}
